We present an approach to learn SAT solver heuristics from scratch through deep reinforcement learning with a curriculum. In particular, we incorporate a graph neural network in a stochastic local search algorithm to act as the variable selection heuristic. We consider Boolean satisfiability problems from different classes and learn specialized heuristics for each class. Although we do not aim to compete with the state-of-the-art SAT solvers in run time, we demonstrate that the learned heuristics allow us to find satisfying assignments in fewer steps compared to a generic heuristic, and we provide analysis of our results through experiments.

This work is original in its use of deep reinforcement learning and graph neural networks to learn novel search control heuristics for SAT solving. While the techniques used are not novel themselves, the application domain is. The authors do a good job of surveying related work in this area and situating their contributions in this landscape. The paper is well-written and I found it very easy to follow the details of the proposed approach and the authors' results. Technically, the work presented is solid, though I have a few comments/suggestions here.

The reviewers were positive about this paper based upon their initial read. The authors response addressed their concerns, so they were even more comfortable with a positive outcome after the author response. I encourage the authors to incorporate their responses to the reviewer concerns into any final version of the paper.

We present an approach to learn SAT solver heuristics from scratch through deep reinforcement learning with a curriculum. In particular, we incorporate a graph neural network in a stochastic local search algorithm to act as the variable selection heuristic. We consider Boolean satisfiability problems from different classes and learn specialized heuristics for each class. Although we do not aim to compete with the state-of-the-art SAT solvers in run time, we demonstrate that the learned heuristics allow us to find satisfying assignments in fewer steps compared to a generic heuristic, and we provide analysis of our results through experiments.

We present an approach to learn SAT solver heuristics from scratch through deep reinforcement learning with a curriculum. In particular, we incorporate a graph neural network in a stochastic local search algorithm to act as the variable selection heuristic. We consider Boolean satisfiability problems from different classes and learn specialized heuristics for each class. Although we do not aim to compete with the state-of-the-art SAT solvers in run time, we demonstrate that the learned heuristics allow us to find satisfying assignments in fewer steps compared to a generic heuristic, and we provide analysis of our results through experiments. Papers published at the Neural Information Processing Systems Conference.